// function insertionSort(arr) {
//     // 默认第0个已经是默认排序好了
//     for (let i = 1; i < arr.length; i++) {
//         // 储存当前位置的值
//         let key = arr[i];
//         let j = i - 1;
//         /*
//         * 当已排序部分的当前元素大于key，
//         * 就将当前元素向后移一位，再将前一位与key比较
//         */
//         while (arr[j] > key) {
//             arr[j + 1] = arr[j];
//             // 往前找比key大的数
//             j--
//         }
//         arr[j + 1] = key;
//     }
//     return arr;
// }

// var a = [4, 0, 1, 3, 2, 6, 17, 419, 22, 46];
// console.log(insertionSort(a));

function insertionSort(arr) {
    for(let i = 1; i < arr.length; i++) {
        let value = arr[i], j = i -1;
        while(arr[j] > value) {
            arr[j+1] = arr[j--]
        }
        arr[j+1] = value
    }
    return arr
}

var a = [4, 0, 1, 3, 2, 6, 17, 419, 22, 46];
console.log(insertionSort(a));